//
// Description: 563. 二叉树的坡度
// Created by Loading on 2021/11/19.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

int findTilt(TreeNode *root) {
    int res = 0;

    function<int(TreeNode *)> dfs = [&](TreeNode *node) {
        if (!node) {
            return 0;
        }

        int left = dfs(node->left);
        int right = dfs(node->right);
        res += abs(left - right);
        return left + right + node->val;
    };
    dfs(root);

    return res;
}

int main() {
    auto root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->right = new TreeNode(1);
    int res = findTilt(root);
    cout << res << endl;

    return 0;
}